'''
https://leetcode.cn/problems/valid-permutations-for-di-sequence/
'''
from functools import cache


class Solution:
    def numPermsDISequence(self, s: str) -> int:
        MOD = 10 ** 9 + 7
        n = len(s)

        # 可以修改为两个可变参数即n_lesser,n_greater要一个即可。
        # 来到第i个位置,
        # 前一个数未知
        # 1) 但是知道了一共使用了多少个数: i
        # 2) 知道有几个数比前一个数小: n_lesser
        # 3) 知道有几个数比前一个数大：n_greater
        @cache
        def f(i, n_lesser, n_greater):
            res = 0
            if i == n:
                res = 1
            elif s[i] == 'D':
                # 下降, 下一个位置可选择的数有n_lesser个，
                # 比我选择的数小的有x个，x属于[0, n_lesser)
                # 比我选择的数大的有y个，y属于(n_lesser, 0] + n_greater
                for x in range(n_lesser):
                    y = n_lesser - 1 - x + n_greater
                    res += f(i + 1, x, y) % MOD
            else:
                # 上升, 下一个位置可选择的数有n_greater个，
                # 比我选择的数小的有x个，x属于(n_greater, 0] + n_lesser
                # 比我选择的数大的有y个，y属于[0, n_greater)
                for y in range(n_greater):
                    x = n_greater - 1 - y + n_lesser
                    res += f(i + 1, x, y) % MOD
            return res % MOD

        # fix -1位置的数
        ans = 0
        for i in range(n + 1):  # 共有n+1个数，比当前小的有[0,n], 比当前大的有[n,0]个
            ans += f(0, i, n - i) % MOD
        return ans % MOD

    # dp打表,没过，超时了，大概是n^4，也就是200^4
    # 记忆化搜索，是因为有的格子压根没走
    def numPermsDISequence2(self, s: str) -> int:
        MOD = 10 ** 9 + 7
        n = len(s)
        dp = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
        # 第一维度依赖后边，第二维度依赖前后，第三维度也是依赖前后
        #   but第二，三维度都是第一维度的前后
        # 初始状态 if i == n: res = 1
        for n_lesser in range(n + 1):
            for n_greater in range(n + 1):
                dp[n][n_lesser][n_greater] = 1
        # 先从大到小推第一维度，第二三维度无所谓顺序
        for i in range(n-1, -1, -1):
            for n_lesser in range(n + 1):
                for n_greater in range(n + 1 - n_lesser):
                    res = 0
                    if s[i] == 'D':
                        for x in range(n_lesser):
                            y = n_lesser - 1 - x + n_greater
                            res += dp[i + 1][x][y] % MOD
                    else:
                        for y in range(n_greater):
                            x = n_greater - 1 - y + n_lesser
                            res += dp[i + 1][x][y] % MOD
                    dp[i][n_lesser][n_greater] = res % MOD

        # fix -1位置的数
        ans = 0
        for i in range(n + 1):  # 共有n+1个数，比当前小的有[0,n], 比当前大的有[n,0]个
            ans += dp[0][i][n - i] % MOD
        return ans % MOD

s = 'IIDDIDDIIDDIDIDDIDDDDIIIDIDIDDDDDIIDIDDIDIIDIDDIIIDIIIIIIIIDIDIDIDDIDIIIIDDIIIIDDDDIIIDDIIDDIDIIIDDDDDDIIDIDDIIDDDDIIDDDIDIDDDIIIDIDIDIIIDDIDDDDDDDDIIDDIDDDIDDDIDDDDIIDIIIDDIDDDIDDIDDDIIDDIIIDIDIIDIDI'
print(len(s))
print(Solution().numPermsDISequence(s))
print(Solution().numPermsDISequence2(s))